package com.example.shirotest.study;

//二叉树遍历
public class BinaryTreeTest {

    public static void main(String[] args) {
        //定义二叉树
        BinaryTree binaryTree = new BinaryTree();

        //定义树节点
        TreeNode node1 = new TreeNode(1, "shongjiang");
        TreeNode node2 = new TreeNode(3, "wuyong");
        TreeNode node3 = new TreeNode(6, "lujunyi");
        TreeNode node4 = new TreeNode(8, "guansheng");
        TreeNode node5 = new TreeNode(10, "lichong");
        TreeNode node6 = new TreeNode(14, "dragon");

        //树节点 =》 树
        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        binaryTree.setRoot(node1);

        //删除节点
        //binaryTree.delNode(5);

        //前序遍历
        //binaryTree.preOrder();

        //中序遍历
       // binaryTree.infixOrder();

        //线索化
        binaryTree.threadedNodes(node1);

        System.out.println(node6.getLeft());
        System.out.println(node6.getRight());

        System.out.println("==================");
        binaryTree.threadedList();


        //后序遍历
        //binaryTree.postOrder();

//        TreeNode treeNode = binaryTree.postSearch(3);
//        if(treeNode != null){
//            System.out.println(treeNode);
//        }else {
//            System.out.println("find nothing");
//        }

    }

}

//二叉树
class BinaryTree{
    private TreeNode root;
    //表示当前节点的前驱节点
    private TreeNode pre;
    
    public void setRoot(TreeNode root){
        this.root = root;
    }

    //前序遍历
    public void preOrder(){
        System.out.println("preOrder:");
        if(this.root != null){
            this.root.preOrder();
        }
    }

    //中序遍历
    public void infixOrder(){
        System.out.println("infixOrder:");
        if(this.root != null){
            this.root.infixOrder();
        }
    }

    //后序遍历
    public void postOrder(){
        System.out.println("postOrder:");
        if(this.root != null){
            this.root.postOrder();
        }
    }

    //前序查找
    public TreeNode preSearch(int id){
        if(this.root == null) return null;
        return this.root.preOrderSearch(id);
    }

    //中序查找
    public TreeNode infixSearch(int id){
        if(this.root == null) return null;
        return this.root.infixOrderSearch(id);
    }

    //后序遍历
    public TreeNode postSearch(int id){
        if(this.root == null) return null;
        return this.root.postOrderSearch(id);
    }

    //删除节点
    public void delNode(int id){
        if(root == null){
            System.out.println("Tree is empty");
            return;
        }

        if(root.getId() == id){
            root = null;
            return;
        }

        //递归删除
        root.delNode(id);
    }


    /**
     * 编写对二叉树进行中序线索化的方法
     * @param node
     */
    public void threadedNodes(TreeNode node){
        if(node == null){
            return;
        }

        //(1)先线索化左子树
        threadedNodes(node.getLeft());

        //(2)再线索化当前节点

        //处理前驱节点
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }

        //处理后继节点
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }

        pre = node;

        //(3)最后线索化右子树
        threadedNodes(node.getRight());

    }

    //中序化：遍历线索化的二叉树
    public void threadedList(){
        TreeNode node = root;
        while (node != null){
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }

            System.out.println(node);

            while (node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }

            node = node.getRight();
        }
    }


}

//树节点
class TreeNode{
    private int id;
    private String name;
    private TreeNode left;
    private TreeNode right;

    //说明
    //1.如果 leftType  == 0 表示当前节点的左指针指向左子树，如为1则表示指向前驱节点
    //2.如果 rightType == 0 表示当前节点的右指针指向右子树，如为1则表示指向后继节点
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public TreeNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }




    //前序遍历方法
    public void preOrder(){
        System.out.println(this); //先输出父节点
        //递归向左子树前序遍历
        if(this.left != null){
            this.left.preOrder();
        }
        //递归右子树前序遍历
        if(this.right != null){
            this.right.preOrder();
        }
    }

    //中序遍历方法
    public void infixOrder(){
        //递归向左子树前序遍历
        if(this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this); //中间输出父节点
        //递归右子树前序遍历
        if(this.right != null){
            this.right.infixOrder();
        }
    }

    //后序遍历方法
    public void postOrder(){
        //递归向左子树前序遍历
        if(this.left != null){
            this.left.postOrder();
        }
        //递归右子树前序遍历
        if(this.right != null){
            this.right.postOrder();
        }
        System.out.println(this); //最后输出父节点
    }


    //前序遍历查找
    public TreeNode preOrderSearch(int id){
        System.out.println("preOrderSearch~~");
        if(this.id == id){
            return this;
        }
        TreeNode treeNode = null;
        if(this.left != null){
           treeNode = this.left.preOrderSearch(id);
        }
        if(treeNode != null){
            return treeNode;
        }
        if(this.right != null){
            treeNode = this.right.preOrderSearch(id);
        }

        return treeNode;
    }


    //中序遍历查找
    public TreeNode infixOrderSearch(int id){
        TreeNode treeNode = null;
        if(this.left != null){
            treeNode = this.left.infixOrderSearch(id);
        }
        if(treeNode != null){
            return treeNode;
        }
        System.out.println("infixOrderSearch~~");
        if(this.id == id){
            return this;
        }
        if(this.right != null){
            treeNode = this.right.infixOrderSearch(id);
        }

        return treeNode;
    }

    //后序遍历查找
    public TreeNode postOrderSearch(int id){
        TreeNode treeNode = null;
        if(this.left != null){
            treeNode = this.left.postOrderSearch(id);
        }
        if(treeNode != null){
            return treeNode;
        }
        if(this.right != null){
            treeNode = this.right.postOrderSearch(id);
        }
        if(treeNode != null){
            return treeNode;
        }
        System.out.println("postOrderSearch~~");
        if(this.id == id){
            return this;
        }

        return treeNode;
    }

    //递归删除节点
    //1、如果删除的节点是叶子节点，则删除该节点
    //2、如果删除的节点是非叶子节点，则删除该子树
    public void delNode(int id){
        if(this.left != null && this.left.id == id){
            this.left = null;
            return;
        }

        if(this.right != null && this.right.id == id){
            this.right = null;
            return;
        }

        if(this.left != null){
            this.left.delNode(id);
        }

        if(this.right != null){
            this.right.delNode(id);
        }
    }

}

